home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / hash / reward.txt < prev    next >
Text File  |  1993-07-23  |  6KB  |  166 lines
  1.  
  2. The one-way hash function, Snefru 2.5, is available
  3. by anonymous FTP from parcftp.xerox.com in directory
  4. /pub/hash.  It is available for use by anyone interested.
  5.  
  6. The $1,000 reward for breaking the 2-pass version of Snefru
  7. was won by Eli Biham, a Ph.D. student of Adi Shamir, in April 1990.
  8.  
  9. A separate $1,000 reward, not yet claimed, is being offered to
  10. the first person to break the 4-pass version of Snefru.
  11.  
  12. General:  Snefru 2.5 is a one-way hash function.  One-way
  13. hash functions have also been called manipulation detection
  14. codes (MDC's), message digests, cryptographically secure
  15. checksums, cryptographically secure hash totals, and sometimes
  16. fingerprints.
  17.  
  18. One way hash functions do not involve use of a secret key
  19. or any secret information.  They are used to authenticate
  20. information, and to verify that the information has not
  21. been tampered with.  One-way hash functions have the
  22. following properties:
  23.  
  24. 1.)  Given any input of any size (a file, for example) it is
  25. easy to compute the output of the one-way hash function.  If
  26. the one-way hash function is designated H, then
  27.       output = H(input)
  28. is easy to compute (takes time linear in the size of the input).
  29.  
  30. 2.)  Although the input might be very large, the output is
  31. relatively small and of fixed size.  In Snefru 2.5, the output
  32. can be either 128 or 256 bits (selectable by the user).
  33.  
  34. 3.)  It is computationally infeasible to find two inputs x and
  35. x' that produce the same output.  That is, finding x and x' such
  36. that:
  37.  
  38.        H(x) = H(x')
  39.  
  40. is infeasible.  Finding such a pair of inputs is known as
  41. "cracking" or "breaking" the one-way hash function.
  42.  
  43. 4.)  Given an output, it is computationally infeasible to
  44. find an input that produces that output.  (This property
  45. is not always used).
  46.  
  47.  
  48. One-way hash functions are not the same as Message Authentication
  49. Codes, or MAC's, which involve the use of a secret key.
  50.  
  51.  
  52.  
  53. History of Snefru:
  54.  
  55. Snefru version 1.0 was designed and made public in early 1989.
  56. No significant security flaws were found at that time in Snefru 1.0,
  57. but several improvements were suggested.  Most significantly, the
  58. tables used in Snefru 1.0 were not generated in a publicly verifiable
  59. fashion.
  60.  
  61. Snefru version 2.0 uses a set of tables generated from publicly
  62. known random information:  "A Million Random Digits with
  63. 100,000 Normal Deviates" by the RAND Corporation, published
  64. by the Free Press in 1955.  In addition, the algorithm used
  65. to derive the tables is also publicly known (and available
  66. for anonymous FTP along with Snefru 2.5).
  67.  
  68. During the redesign, the basic algorithm was made simpler
  69. and some features of modest utility which increased the
  70. complexity of the design were eliminated.  The revisions
  71. for Snefru 2.0 were completed in July.  The C source for
  72. Snefru 2.0 was made available by anonymous FTP in November
  73. of 1989.
  74.  
  75.  
  76. Security of Snefru:
  77.  
  78. The security of one-way hash functions can (at present) only
  79. be assessed by making them widely available for review and
  80. attack.  At the present time, Snefru has undergone some internal
  81. review at Xerox and has been subjected to two separate and
  82. independent reviews by two outside consultants hired
  83. for the purpose.  Following general distribution of Snefru
  84. for analysis and attack, Eli Biham broke the 2-pass version
  85. of Snefru in April 1990 and won the $1,000 prize being
  86. offered for such a break.
  87.  
  88. The difficulty of breaking such systems normally goes up
  89. sharply with the number of passes.  The default number of
  90. passes has been increased to 8.  A new reward of
  91. $1,000 is being offered to the first person to break the
  92. 4-pass version.
  93.  
  94. In view of Eli's successful attack on the 2-pass version, it
  95. would be prudent to wait until he (and others) have had a
  96. chance to review the strength of the 4-pass version.
  97.  
  98. And, of course, Xerox Corporation makes no representations
  99. concerning either the merchantability of Snefru or the suitability
  100. of Snefru for any particular purpose.  It is provided "as is"
  101. without express or implied warranty of any kind.
  102.  
  103. To encourage examination of the 4-pass version of Snefru,
  104. a reward of $1,000 is offered to the first person who shows
  105. they have broken it.  A "break" is defined as providing
  106. two different inputs that produce the same output.
  107. The output size will be 128 bits, and the "security level"
  108. parameter will be set at 4.  (Note that a larger output size
  109. (256 bits) is available in Snefru 2.5 as an option).
  110.  
  111. Fine print:  Xerox employees cannot enter.  The winner must send his
  112. name, address, and social security number along with the
  113. inputs x and x' that produce the same output.  It is expected that
  114. other relevant information (the nature of the algorithm used, the
  115. hardware, etc) will also be sent, though this is not required.  Any
  116. taxes are the responsibility of the winner.   We reserve the right
  117. to decide ties (multiple entries on or about the same date) and our
  118. decision will be final.
  119.  
  120.  
  121. Implementation:
  122.  
  123. Snefru version 2.5a supports 8 passes.  It is algorithmically identical
  124. to versions 2.0, 2.1, 2.2, and 2.3.  The default setting for the number
  125. of passes in 2.5a has been changed to 8.  By setting the number of passes
  126. to 2 or 4, the results can be made identical with the earlier versions.
  127. In the author's opinion, further security analysis of Snefru is required
  128. before it can be considered for production use.
  129.  
  130.  
  131.  
  132.  
  133. Free Availability:
  134.  
  135. Anyone who wishes to use Snefru can do so without charge.
  136. The following notices appear in the source, and are the only
  137. restrictions on the use of Snefru:
  138.  
  139. Copyright (c) Xerox Corporation 1989.  All rights reserved.
  140.  
  141. License to copy and use this software is granted provided
  142. that it is identified as the "Xerox Secure Hash Function"
  143. in all material mentioning or referencing this software
  144. or this hash function.
  145.  
  146. License is also granted to make and use derivative works
  147. provided that such works are identified as "derived from
  148. the Xerox Secure Hash Function" in all material mentioning
  149. or referencing the derived work.
  150.  
  151. Xerox Corporation makes no representations concerning either
  152. the merchantability of this software or the suitability of
  153. this software for any particular purpose.  It is provided
  154. "as is" without express or implied warranty of any kind.
  155.  
  156.  
  157.  
  158. Re-posting of this announcement to appropriate groups is encouraged.
  159.  
  160.  
  161. Ralph C. Merkle
  162. merkle@xerox.com
  163. Xerox PARC
  164. 3333 Coyote Hill Road
  165. Palo Alto, CA 94304
  166.